'''

测试快速排序

'''
arr=[4,5,2,8,3]
def Quick_sort(arr):
	if len(arr) > 2:
		pivot = arr[0]
		left = 1
		right = len(arr)-1
		arr1,arr2 = [],[]
		while left < right:
			if arr[left] < pivot:
				arr1.append(arr[left])
				left+=1
			elif arr[left] > pivot:
				arr2.append(arr[left])
				left+=1
			if arr[right] < pivot:
				arr1.append(arr[right])
				right -= 1
			elif arr[right] > pivot:
				arr2.append(arr[right])
				right -= 1
		arr1 = Quick_sort(arr1)
		arr2 = Quick_sort(arr2)
	elif len(arr)==1:
		return arr
	elif len(arr)==2:
		if arr[0] > arr[1]:
			return [arr[1],arr[0]]
		else:
			return arr
	arr1 = Quick_sort(arr1)
	arr2 = Quick_sort(arr2)
	return arr1+[pivot]+arr2
Quick_sort(arr)